package com.fr.lintcode;

import java.util.Stack;

import org.junit.Test;

/**
*作者：furong
*日期：2017年2月14日
*时间：上午10:52:29
*/
public class Q552iii {
    /**
     * @param nums1 an integer array of length m with digits 0-9
     * @param nums2 an integer array of length n with digits 0-9
     * @param k an integer and k <= m + n
     * @return an integer array
     */
    public int[] maxNumber(int[] nums1, int[] nums2, int k) {
        Stack<Integer> s1 = new Stack<>();
        build(nums1, s1);
        reversal(s1);
        Stack<Integer> s2 = new Stack<>();
        build(nums2, s2);
        reversal(s2);
        int rs[] = new int[k];
        return rs;
    }

    private void reversal(Stack<Integer> s) {
        int n = s.size();
        int tmp[] = new int[n];
        int i = 0;
        while (!s.isEmpty()) {
            tmp[i++] = s.pop();
        }
        for (int j : tmp) {
            s.push(j);
        }
    }

    private void build(int[] nums, Stack<Integer> s) {
        for (int i = 0; i < nums.length; i++) {
            while (!s.empty()) {
                if (nums[s.peek()] < nums[i]) {
                    s.pop();
                } else {
                    s.push(i);
                    break;
                }
            }
            if (s.empty()) {
                s.push(i);
            }
        }
    }

    @Test
    public void TestA() {
        // [5,0,2,1,0,1,0,3,9,1,2,8,0,9,8,1,4,7,3], [7,6,7,1,0,1,0,5,6,0,5,0], 31
        // int[] a = { 5, 0, 2, 1, 0, 1, 0, 3, 9, 1, 2, 8, 0, 9, 8, 1, 4, 7, 3 };
        // int[] b = { 7, 6, 7, 1, 0, 1, 0, 5, 6, 0, 5, 0 };
        // int k = 31;
        int[] a = { 1, 5, 8, 1, 4, 0, 8, 5, 0, 7, 0, 5, 7, 6, 0, 5, 5, 2, 4, 3, 6, 4, 6, 6, 3, 8, 1, 1, 3, 1, 3, 5, 4, 3, 9, 5, 0, 3, 8, 1, 4, 9, 8, 8, 3, 4,
                6, 2, 5, 4, 1, 1, 4, 6, 5, 2, 3, 6, 3, 5, 4, 3, 0, 7, 2, 5, 1, 5, 3, 3, 8, 2, 2, 7, 6, 7, 5, 9, 1, 2 };
        int[] b = { 7, 8, 5, 8, 0, 1, 1, 6, 1, 7, 6, 9, 6, 6, 0, 8, 5, 8, 6, 3, 4, 0, 4, 6, 7, 8, 7, 7, 7, 5, 7, 2, 5, 2, 1, 9, 5, 9, 3, 7, 3, 9, 9, 3, 1, 4,
                3, 3, 9, 7, 1, 4, 4, 1, 4, 0, 2, 3, 1, 3, 2, 0, 2, 4, 0, 9, 2, 0, 1, 3, 9, 1, 2, 2, 6, 6, 9, 3, 6, 0 };
        int k = 80;
        int[] rs = maxNumber(a, b, k);
        for (int s : rs) {
            System.out.print(s + ",");
        }
    }
}
